package com.leet.code.lcof;

import java.util.Arrays;

public class Code57 {

    public static void main(String[] args) {
        int[] nums = {14, 15, 16, 22, 53, 60};
        System.out.println(Arrays.toString(new Code57().twoSum(nums, 76)));
    }


    public int[] twoSum(int[] nums, int target) {
        int i1 = 0;
        int i2 = nums.length - 1;

        while (i1 != i2) {
            if (nums[i1] + nums[i2] == target) {
                return new int[]{nums[i1], nums[i2]};
            }
            if (nums[i1] + nums[i2] > target) {
                i2--;
            } else {
                i1++;
            }

        }
        return new int[0];
    }

    public int[] twoSum1(int[] nums, int target) {
        int i = 0, a = nums[i], b = target - a, s = 1, e = nums.length - 1;
        int j = search(nums, b, s, e);
        int b1 = nums[j];
        while (b != b1) {
            a = nums[++i];
            b = target - a;
            s = i + 1;
            e = j;
            j = search(nums, b, s, e);
            b1 = nums[j];
        }

        return new int[]{a, b};

    }

    public int search(int[] nums, int target, int start, int end) {
        int mid = 0;

        while (start <= end) {

            mid = start + ((end - start) >> 1);

            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }


        }

        return mid;
    }


}
